#include <iostream>
using namespace std;

struct ListNode
{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
	ListNode(int Arr[], int len)
	{
		this->val = Arr[0];
		this->next = NULL;
		ListNode *pp = this;
		for (int i = 1; i < len; i++)
		{
			ListNode *p = new ListNode(Arr[i]);
			pp->next = p;
			pp = p;
		}
	}

	void print()
	{
		ListNode *p = this;
		while (p != NULL)
		{
			cout << p->val << " ";
			p = p->next;
		}
	}
};

// 94.87 %
class Solution
{
  public:
	ListNode *reverseList(ListNode *head)
	{
		ListNode *pre = NULL, *cur = head;
		while (cur)
		{
			ListNode *nex = cur->next;
			cur->next = pre;
			pre = cur;
			cur = nex;
		}
		return pre;
	}
};

int main()
{
	int Arr[] = {1, 2, 3, 4, 5};
	int length = sizeof(Arr) / sizeof(Arr[0]);
	ListNode *list = new ListNode(Arr, length);
	list->print();
	cout << endl;
	list = Solution().reverseList(list);
	list->print();
	return 0;
}
